/**
 * @author VernHe
 * @date 2021年11月01日 13:54
 * <p>
 * <p>
 * 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
 * <p>
 * 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为NULL 的节点将直接作为新二叉树的节点。
 * <p>
 * 示例1:
 * <p>
 * 输入:
 * Tree 1                     Tree 2
 * 1                         2
 * / \                       / \
 * 3   2                     1   3
 * /                           \   \
 * 5                             4   7
 * 输出:
 * 合并后的树:
 * 3
 * / \
 * 4   5
 * / \   \
 * 5   4   7
 */
public class Solution_0617 {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (null == root1) {
            return root2;
        }
        if (null == root2) {
            return root1;
        }
        TreeNode result = new TreeNode();
        doMergeTrees(root1, root2, result);
        return result;
    }

    private void doMergeTrees(TreeNode node1, TreeNode node2, TreeNode mergedNode) {

        int val1 = null == node1 ? 0 : node1.val;
        int val2 = null == node2 ? 0 : node2.val;
        mergedNode.val = val1 + val2;


        if ((null != node1 && null != node1.left) || (null != node2 && null != node2.left)) {
            // 左边如果有值，就new一个节点用于合并
            mergedNode.left = new TreeNode();
            doMergeTrees(null != node1 ? node1.left : null, null != node2 ? node2.left : null, mergedNode.left);
        } else {
            // 都为null就不进行合并
            mergedNode.left = null;
        }

        if ((null != node1 && null != node1.right) || (null != node2 && null != node2.right)) {
            // 右边如果右节点就new一个节点用于合并
            mergedNode.right = new TreeNode();
            doMergeTrees(null != node1 ? node1.right : null, null != node2 ? node2.right : null, mergedNode.right);
        } else {
            mergedNode.right = null;
        }

    }

    private void doMergeTrees2 (TreeNode node1, TreeNode node2, TreeNode mergedNode){
        int val1 = 0, val2 = 0;
        TreeNode leftNode1 = null, rightNode1 = null, leftNode2 = null, rightNode2 = null;
        if (null != node1) {
            val1 = node1.val;
            leftNode1 = node1.left;
            rightNode1 = node1.right;
        }

        if (null != node2) {
            val2 = node2.val;
            leftNode2 = node2.left;
            rightNode2 = node2.right;
        }

        mergedNode.val = val1 + val2;


        if (null != leftNode1 || null != leftNode2) {
            // 左边如果有值，就new一个节点用于合并
            mergedNode.left = new TreeNode();
            doMergeTrees2(null != node1 ? node1.left : null, null != node2 ? node2.left : null, mergedNode.left);
        } else {
            // 都为null就不进行合并
            mergedNode.left = null;
        }

        if (null != rightNode1 || null != rightNode2) {
            // 右边如果右节点就new一个节点用于合并
            mergedNode.right = new TreeNode();
            doMergeTrees2(null != node1 ? node1.right : null, null != node2 ? node2.right : null, mergedNode.right);
        } else {
            mergedNode.right = null;
        }

    }

    public static void main(String[] args) {
//        TreeNode root1 = new TreeNode(1);
//        root1.left = new TreeNode(3);
//        root1.left.left = new TreeNode(5);
//        root1.right = new TreeNode(2);
//
//        TreeNode root2 = new TreeNode(2);
//        root2.left = new TreeNode(1);
//        root2.left.right = new TreeNode(4);
//        root2.right = new TreeNode(3);
//        root2.right.right = new TreeNode(7);


        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(4);
        root1.left.left = new TreeNode(1);
        root1.left.left.left = new TreeNode(0);
        root1.left.right = new TreeNode(2);
        root1.right = new TreeNode(5);

        TreeNode root2 = new TreeNode(4);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(2);

        new Solution_0617().mergeTrees(root1, root2);
    }
}
